//
//  24.二叉树中和为某一值的路径.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/20.
//

import Foundation
/*
 题目：输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
 思路1：深度优先搜索。使⽤前序遍历，使⽤两个全局变量result和tmp，result来存放最终结果，tmp⽤来存放临时结果。 每次遍历，我们先把root的值压⼊tmp，然后判断当前root是否同时满⾜： 与给定数值相减为0； 左⼦树为空； 右⼦树为空。 如果满⾜条件，就将tmp压⼊result中，否则，依次遍历左右⼦树。需要注意的是，遍历左右⼦树的时候，全局变量tmp是不清空的，直到到了根结点才 请空tmp。
 */
func offer_24() {
    let root = BinaryTreeNode(1)
    root.leftNode = {
        let node = BinaryTreeNode(2)
        node.leftNode = BinaryTreeNode(4)
        node.rightNode = BinaryTreeNode(5)
        return node
    }()
    root.rightNode = {
        let node = BinaryTreeNode(3)
        node.leftNode = BinaryTreeNode(6)
        node.rightNode = BinaryTreeNode(7)
        return node
    }()
    print(Solution().findPath2(root, 11))
}

fileprivate class Solution {
    private var result = [[Int]]()
    private var temp = [Int]()
    
    @discardableResult
    func findPath1(_ root: BinaryTreeNode<Int>?, _ expectNumber: Int) -> [[Int]] {
        // write code here
        guard let root = root else { return result }
        temp.append(root.data)
        if expectNumber - root.data == 0 && root.leftNode == nil && root.rightNode == nil {
            result.append(temp)
        }
        if expectNumber - root.data > 0 {
            findPath1(root.leftNode, expectNumber - root.data)
            findPath1(root.rightNode, expectNumber - root.data)
        }
        temp.removeLast()
        return result
    }
}

/*
 题目：输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
 思路2：栈替代递归
 */
extension Solution {
    func findPath2(_ root: BinaryTreeNode<Int>?, _ expectNumber: Int) -> [[Int]] {
        // write code here
        guard let root = root else { return [] }
        var result = [[Int]]()
        // 栈存放的是节点和当前路径
        var stack = [(BinaryTreeNode<Int>, [Int])]()
        stack.append((root, [root.data]))
        while !stack.isEmpty {
            let (node, path) = stack.removeLast()
            let sum = path.reduce(0, +)
            if sum == expectNumber && node.leftNode == nil && node.rightNode == nil {
                result.append(path)
            } else if sum < expectNumber {
                // 为了保持跟递归一样的顺序，先右后左
                if let left = node.rightNode {
                    stack.append((left, path+[left.data]))
                }
                if let right = node.leftNode {
                    stack.append((right, path+[right.data]))
                }
            }
        }
        return result
    }
}
